/*
 * @lc app=leetcode id=221 lang=cpp
 *
 * [221] Maximal Square
 */
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if (row < 1) {
            return 0;
        }
        int col = matrix[0].size();

        int size = 0;
        vector<vector<int>> memo(row, vector<int>(col, 0));
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (i==0 || j==0 || matrix[i][j]=='0') {
                    memo[i][j] = matrix[i][j] - '0';
                } else {
                    memo[i][j] = std::min(memo[i-1][j-1], std::min(memo[i-1][j], memo[i][j-1])) + 1;
                }
                if (memo[i][j] > size) {
                    size = memo[i][j];
                }
            }
        }
        return size*size;

    }
};

